#define _CRT_SECURE_NO_WARNINGS
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int m = 0;
        for (int i = n - 1; i >= 2; i--) {
            int left = 0;
            int right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] + nums[i] > 0) right--;
                else if (nums[left] + nums[right] + nums[i] < 0) left++;
                else {
                    m++;
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1] && left < n) left++;
                    while (left < right && nums[right] == nums[right + 1] && right >= 0) right--;

                }
            }
            while (nums[i] == nums[i - 1] && i >= 2) i--;

        }
        vector<vector<int>>f(m, vector<int>(3));
        int ret = 0;
        for (int i = n - 1; i >= 2; i--) {
            int left = 0;
            int right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] + nums[i] > 0) right--;
                else if (nums[left] + nums[right] + nums[i] < 0) left++;
                else {
                    f[ret][0] = nums[left];
                    f[ret][1] = nums[right];
                    f[ret][2] = nums[i];
                    ret++;
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1] && left < n) left++;
                    while (left < right && nums[right] == nums[right + 1] && right >= 0) right--;
                }
            }
            while (nums[i] == nums[i - 1] && i >= 2) i--;

        }
        return f;
    }
};
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>>f;
        sort(nums.begin(), nums.end());
        for (int i = n - 1; i >= 2; i--) {
            if (nums[i] < 0) break;
            int left = 0;
            int right = i - 1;
            int target = -nums[i];
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum > target) right--;
                else if (sum < target) left++;
                else {
                    f.push_back({ nums[left],nums[right],nums[i] });
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            while (i > 2 && nums[i] == nums[i - 1])i--;
        }
        return f;
    }
};
int main() {
   /* Solution a;
    vector<int>f(4);*/
    int arr[10] = { 0 };
    arr[1] = 1;
    1[arr] = 2;
    //a.threeSum(f);
}//
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>>f;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i <= n - 4; i++) {

            for (int j = i + 1; j <= n - 3; j++) {
                long long t1 = (long long)target - nums[j] - nums[i];
                int left = j + 1, right = n - 1;
                while (left < right) {
                    int sum = nums[left] + nums[right];
                    if (sum < t1) left++;
                    else if (sum > t1) right--;
                    else {
                        f.push_back({ nums[i],nums[j],nums[left],nums[right] });
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                while (j <= n - 3 && nums[j] == nums[j + 1]) j++;
            }
            while (i <= n - 4 && nums[i] == nums[i + 1])i++;
        }
        return f;
    }
};
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        int len = n + 1;
        for (int left = 0, right = 0; right < n; right++) {
            sum += nums[right];
            while (sum >= target) {
                len = min(len, right - left + 1);
                sum -= nums[left++];
            }
        }
        return len == n + 1 ? 0 : len;
    }
};
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int hash[128] = { 0 };
        int left = 0, right = 0;
        int ret = 0;
        while (right < n) {
            hash[s[right]]++;
            while (hash[s[right]] > 1) {
                hash[s[left++]]--;
            }
            ret = max(ret, right - left + 1);
            right++;
        }
        return ret;
    }
};
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        int s = 0;
        for (int i = 0; i < n; i++) {
            int z = 0;
            int ret = 0;
            for (int j = i; j < n; j++) {
                if (nums[j] == 0)z++;
                ret = j - i + 1;
                if (z == k + 1) {
                    s = max(s, ret - 1);
                    break;
                }
                s = max(s, ret);
            }
        }
        return s;
    }
};
 class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        int left = 0, right = 0;
        int z = 0;
        int s = 0;
        while (right < n) {
            if (nums[right] == 0)z++;
            while (z > k) {
                if (nums[left] == 0) {
                    left++;
                    z--;
                }
                else  left++;
            }

            s = max(s, right - left + 1);
            right++;
        }
        return s;
    }
};
 class Solution {
 public:
     int minSubArrayLen(int target, vector<int>& nums) {
         int n = nums.size();
         int ret = 100000;
         int sum = 0;
         for (int left = 0, right = 0; right < n; right++) {
             sum += nums[right];
             if (sum < target)continue;
             else {
                 ret = min(ret, right - left + 1);
                 while (sum >= target) {
                     sum -= nums[left];
                     left++;
                 }
                 ret = min(ret, right - left + 2);

             }
         }
         return ret == 100000 ? 0 : ret;
     }
 };
 class Solution {
 public:
     int minSubArrayLen(int target, vector<int>& nums) {
         int n = nums.size();
         int ret = 100000;
         int sum = 0;
         for (int left = 0, right = 0; right < n; right++) {
             sum += nums[right];
             if (sum >= target) {
                 while (sum >= target) {
                     sum -= nums[left++];
                 }
                 ret = min(ret, right - left + 2);
             }
         }
         return ret == 100000 ? 0 : ret;
     }
 };
 class Solution {
 public:
     int lengthOfLongestSubstring(string s) {
         int n = s.size();
         int hash[128] = { 0 };
         int ret = 0;
         for (int left = 0, right = 0; right < n; right++) {
             hash[s[right]]++;
             while (hash[s[right]] >= 2) {
                 hash[s[left++]]--;
             }
             ret = max(ret, right - left + 1);
         }
         return ret;
     }
 };
 class Solution {
 public:
     int longestOnes(vector<int>& nums, int k) {
         int n = nums.size();
         int zero = 0;
         int ret = 0;
         for (int left = 0, right = 0; right < n; right++) {
             if (nums[right] == 0)zero++;
             while (zero > k) {
                 if (nums[left++] == 0) {
                     zero--;
                 }
             }
             ret = max(ret, right - left + 1);
         }
         return ret;
     }
 };
 class Solution {
 public:
     int minOperations(vector<int>& nums, int x) {
         int n = nums.size();
         int s = 0;
         for (int i = 0; i < n; i++)s += nums[i];
         int target = s - x;
         if (target < 0)return -1;
         int sum = 0, ret = -1;
         for (int left = 0, right = 0; right < n; right++) {
             sum += nums[right];
             while (sum > target) {
                 sum -= nums[left++];
             }
             if (sum == target) {
                 int len = right - left + 1;
                 ret = max(ret, len);
             }
         }
         return ret == -1 ? -1 : n - ret;
     }
 };
 class Solution {
 public:
     int totalFruit(vector<int>& fruits) {
         int n = fruits.size();
         int tmax = 0;
         for (int i = 0; i < n; i++)
         {
             tmax = max(tmax, fruits[i]);
         }
         int* arr = (int*)calloc(tmax + 1, 4);
         int kind = 0;
         int ret = 0;
         for (int left = 0, right = 0; right < n; right++) {
             arr[fruits[right]]++;
             if (arr[fruits[right]] == 1)kind++;
             while (kind > 2) {
                 arr[fruits[left]]--;
                 if (arr[fruits[left]] == 0)kind--;
                 left++;
             }
             int sum = right - left + 1;
             ret = max(ret, sum);
         }
         return ret;
     }
 };
 class Solution {
 public:
     vector<int> findAnagrams(string s, string p) {
         int n = s.size();
         int m = p.size();
         vector<int>(f);

         if (m > n)return f;
         int arr[123] = { 0 };
         int a[123] = { 0 };
         for (int i = 0; i < m; i++) {
             arr[p[i]]++;
             a[s[i]]++;
         }
         for (int left = 0, right = m - 1; right < n; right++, left++) {
             int sign = 1;
             for (int i = 97; i <= 122; i++) {
                 if (arr[i] != a[i]) {
                     sign = 0;
                     break;
                 }
             }
             if (sign == 1)f.push_back({ left });
             a[s[left]]--;
             a[s[right + 1]]++;

         }
         return f;
     }
 };
 class Solution {
 public:
     vector<int> findAnagrams(string s, string p) {
         int n = s.size();
         int n1 = p.size();
         vector<int>(f);
         int arr[123] = { 0 };
         int arr1[123] = { 0 };
         for (int i = 0; i < n1; i++) {
             arr1[p[i]]++;
         }
         int count = 0;
         for (int left = 0, right = 0; right < n; right++) {
             arr[s[right]]++;
             if (arr[s[right]] <= arr1[s[right]])count++;
             if (right - left + 1 > n1) {
                 char out = s[left];
                 left++;
                 if (arr[out] <= arr1[out])count--;
                 arr[out]--;
             }
             if (count == n1)f.push_back(left);
         }
         return f;
     }
 };
#include <iostream>
#include<string>
 using namespace std;

 int main() {
     string s;
     getline(cin, s);
     int n = s.size();
     int num = 0;
     int tmp = 0;
     int pos = 0;
     for (int i = 0; i <= n; i++) {
         if (s[i] >= '0' && s[i] <= '9')tmp++;
         else {
             num = max(num, tmp);
             if (num == tmp)pos = i - num;
             tmp = 0;
         }
     }
     cout << s.substr(pos, num);
 }
 int main() {
     string s, s1, s2;
     getline(cin, s);
     for (int i = 0; i <= s.size(); i++) {
         if (s[i] >= '0' && s[i] <= '9')s1 += s[i];
         else {
             if (s1.size() > s2.size())s2 = s1;

             s1.clear();
         }
     }
     cout << s2;
 }
 int MoreThanHalfNum_Solution(vector<int>& numbers) {
     // write code here
     int ret = -1;
     int num = 0;
     for (auto e : numbers) {
         if (ret == -1) {
             ret = e;
             num++;
         }
         else if (ret != e) {
             num--;
             if (num == 0) {
                 ret = -1;
                 num = 0;
             }
         }
         else num++;
     }
     return ret;

 }
};
int main() {
    int t1 = 0, t2 = 0, t3 = 0, t4 = 0;
    cin >> t1 >> t2 >> t3 >> t4;
    int a = (t1 + t3) / 2;
    int b1 = (t2 + t4) / 2;
    int b2 = (t3 - t1) / 2;
    int c = (t4 - t2) / 2;
    if (b1 == b2)cout << a << ' ' << b1 << ' ' << c;
    else cout << "No";
}
#include <iostream>
#include<string>
#include<algorithm>
using namespace std;

int main() {
    int m = 0;
    int n = 0;
    cin >> m >> n;
    int sign = 1;
    if (m < 0) {
        m = -m;
        sign = -1;
    }
    string s;
    while (m != 0) {
        s += (m % n + '0');
        m /= n;
    }

    reverse(s.begin(), s.end());
    if (sign == -1)cout << '-';
    if (s.size() == 0)cout << 0;
    else
        for (auto e : s) {
            printf("%X", e - '0');
        }
}
#include <iostream>
#include<string>
using namespace std;
int isnum(string s) {
    int n = s.size();
    int left = 0;
    int right = n - 1;
    while (left < right) {
        if (s[left] != s[right])return 0;
        left++;
        right--;
    }
    return 1;
}
int main() {
    string a;
    string b;
    getline(cin, a);
    getline(cin, b);
    int n = a.size();
    int sum = 0;
    for (int i = 0; i <= n; i++) {
        string s3;
        s3 += a.substr(0, i);
        s3 += b;
        s3 += a.substr(i);
        sum += isnum(s3);
    }
    cout << sum;
}
#include <climits>
#include <iostream>
#include<vector>
using namespace std;

int main() {
    int n = 0;
    cin >> n;
    vector<int>f(n);
    for (auto& e : f) {
        cin >> e;
    }
    vector<int>g(n);
    g[0] = f[0];
    for (int i = 1; i < n; i++) {
        g[i] = max(g[i - 1] + f[i], f[i]);
    }
    int tmax = -0xffff;
    for (auto e : g)tmax = max(tmax, e);
    cout << tmax << endl;
}
class Solution {
public:
    int StrToInt(string str) {
        int n = str.size();
        int sign = 1;
        int i = 0;
        if (str[0] == '+' || str[0] == '-')i = 1;
        if (str[0] == '-')sign = -1;
        int num = 1;
        int sum = 0;
        for (int j = n - 1; j >= i; j--) {
            if (str[j] >= '0' && str[j] <= '9') {
                sum += num * (str[j] - '0');
                num *= 10;
            }
            else return 0;
        }
        sum *= sign;
        return sum;
    }
};
#include <iostream>
#include<vector>
using namespace std;

int main() {
    int w = 0;
    int h = 0;
    cin >> w >> h;
    vector<vector<int>>f(h, vector<int>(w, 1));
    int sum = 0;

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (f[i][j] == 1) {
                sum++;
                if (i + 2 < w)f[i + 2][j] = 0;
                if (j + 2 < h)f[i][j + 2] = 0;
            }
        }
    }

    cout << sum << endl;
    return 0;
}
#include <iostream>
#include<vector>
using namespace std;
int main() {
    int w = 0;
    int h = 0;
    cin >> w >> h;
    vector<vector<int>>f(h, vector<int>(w, 1));
    int sum = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (f[i][j] == 1) {
                sum++;
                if (i + 2 < h)f[i + 2][j] = 0;
                if (j + 2 < w)f[i][j + 2] = 0;
            }
        }
    }
    cout << sum << endl;
    return 0;
}
#include <iostream>
using namespace std;

int main() {
    int n = 0;
    cin >> n;
    int a1 = 0, a2 = 1, a3 = 1;
    int l = 0;
    int r = 0;
    while (1) {
        a3 = a1 + a2;
        a1 = a2;
        a2 = a3;
        if (a3 <= n)l = n - a3;
        if (a3 > n) {
            r = a3 - n;
            break;
        }
    }
    cout << min(r, l);
}
class Parenthesis {
public:
    bool chkParenthesis(string a, int n) {
        // write code here
        string s;
        for (int i = 0; i < n; i++) {
            if (a[i] == '(')s += '(';
            else if (a[i] == ')') {
                if (s[s.size() - 1] == '(')s.pop_back();
                else return false;
            }
            else return false;
        }
        if (s.size() == 0)return true;
        return false;
    }
};
#include <iostream>
#include<string>
#include<vector>
using namespace std;

int main() {
    int n = 0;
    cin >> n;

    vector<string>a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int l = 1;
    int s = 1;
    int i = 0;
    while ((i < n - 1) && (l == 1 || s == 1)) {
        if (l == 1) {
            if (a[i] >= a[i + 1])l = 0;
        }
        if (s == 1) {
            if (a[i].size() >= a[i + 1].size())s = 0;

        }
        i++;
    }
    if (s == 1 && l == 1)cout << "both" << endl;
    if (s != 1 && l != 1)cout << "none" << endl;
    if (l == 1 && s != 1)cout << "lexicographically" << endl;
    if (l != 1 && s == 1)cout << "lengths" << endl;
}
#include <iostream>
using namespace std;

int main() {
    int a = 0;
    int b = 0;
    cin >> a >> b;
    int c = a;
    int d = b;
    int tmp = a % b;
    while (tmp != 0) {
        a = b;
        b = tmp;
        tmp = a % b;
    }
    cout << c * d / b;
}